package leetcode.editor.cn.dsa19_trie;
//实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。
//
// 示例: 
// Trie trie = new Trie();
//trie.insert("apple");
//trie.search("apple");   // 返回 true
//trie.search("app");     // 返回 false
//trie.startsWith("app"); // 返回 true
//trie.insert("app");   
//trie.search("app");     // 返回 true 
//
// 说明: 
// 你可以假设所有的输入都是由小写字母 a-z 构成的。
// 保证所有输入均为非空字符串。 
// 
// Related Topics 设计 字典树 
// 👍 492 👎 0

public class ImplementTriePrefixTree208 {
    //leetcode submit region begin(Prohibit modification and deletion)
    class Trie {
        class TrieNode {
            private final int SIZE = 26;
            TrieNode[] child;
            boolean isWord;

            public TrieNode() {
                child = new TrieNode[SIZE];
            }
        }

        private TrieNode root;

        /**
         * Initialize your data structure here.
         */
        public Trie() {
            root = new TrieNode();
        }

        /**
         * Inserts a word into the trie.
         */
        public void insert(String word) {
            TrieNode presentNode = root;
            // 遍历待插入单词的每一个字符
            for (int i = 0; i < word.length(); i++) {
                int wordPos = word.charAt(i) - 'a'; // 计算字符位置
                if (presentNode.child[wordPos] == null) {
                    // 指定位置节点不存在则创建
                    presentNode.child[wordPos] = new TrieNode();
                }
                // 指针移动到下一层节点
                presentNode = presentNode.child[wordPos];
            }
            presentNode.isWord = true; // 标记一个单词
        }

        /**
         * Returns if the word is in the trie.
         */
        public boolean search(String word) {
            TrieNode presentNode = root;
            for (int i = 0; i < word.length(); i++) {
                int wordPos = word.charAt(i) - 'a';
                if (presentNode.child[wordPos] == null) {
                    return false;
                }
                presentNode = presentNode.child[wordPos];
            }
            return presentNode.isWord; // 判断最后一个节点是否为单词
        }

        /**
         * Returns if there is any word in the trie that starts with the given prefix.
         */
        public boolean startsWith(String prefix) {
            TrieNode presentNode = root;
            for (int i = 0; i < prefix.length(); i++) {
                int wordPos = prefix.charAt(i) - 'a';
                if (presentNode.child[wordPos] == null) {
                    return false;
                }
                presentNode = presentNode.child[wordPos];
            }
            return true; // 能找到前缀所有字符则返回true
        }
    }
    /**
     * Your Trie object will be instantiated and called as such:
     * Trie obj = new Trie();
     * obj.insert(word);
     * boolean param_2 = obj.search(word);
     * boolean param_3 = obj.startsWith(prefix);
     */
    //leetcode submit region end(Prohibit modification and deletion)
}